import java.util.*;

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {

        int size = m + n;
        for (int i = m; i < size; i++) {
            nums1[i] = nums2[i - m];
        }
//        // 冒泡排序
//        for (int i = 0; i < size-1; i++) {
//            for (int j = 0; j < size-1-i; j++) {
//                if (nums1[j]>nums1[j+1]){
//                    int temp = nums1[j];
//                    nums1[j] = nums1[j+1];
//                    nums1[j+1] = temp;
//                }
//            }
//        }
//        //
        Arrays.sort(nums1);

    }


    public int removeElement(int[] nums, int val) {
        int count = 0;
        int temp = 0;
        for (int i = 0; i < nums.length - count; i++) {
            if (nums[i] == val) {
                count++;
                temp = nums[i];
                nums[i] = nums[nums.length - count];
                nums[nums.length - count] = temp;
                i--;
            }
        }
        return nums.length - count;
    }

    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        LinkedHashSet<Integer> set = new LinkedHashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        int i = 0;
        for (Integer integer : set) {
            nums[i++] = integer;
        }
        return set.size();

    }

    public int removeDuplicates_2(int[] nums) {
        if (nums.length > 2 && nums[0] == nums[nums.length - 1]) {
            return 2;
        }
        int start = 0;
        int count = 0;
        for (int i = 0; i < nums.length - count; i++) {
            if (nums[i] == nums[start]) {
                if (i > start + 1) {
                    while (nums[i] == nums[start]) {
                        if (nums[i] == nums[nums.length - 1 - count]) {
                            return i;
                        }

                        // 让此位的数据移到数组末尾
                        for (int j = i; j < nums.length - 1 - count; j++) {
                            int temp = nums[j];
                            nums[j] = nums[j + 1];
                            nums[j + 1] = temp;
                        }
                        count++;
                        if (i >= nums.length - 1) {
                            break;
                        }
                    }
                    start = i;
//                    i--;
                }
            } else {
                start = i;
            }
        }
        return nums.length - count;
    }

    public int majorityElement(int[] nums) {
//        HashMap<Integer, Integer> map = new HashMap();
//
//        for (int i = 0; i < nums.length; i++) {
//            if (map.containsKey(nums[i])){
//                map.put(nums[i],map.get(nums[i])+1);
//            }else{
//                map.put(nums[i],1);
//            }
//        }
//        Set<Integer> set = map.keySet();
//        for (Integer i : set) {
//            if (map.get(i)>nums.length/2){
//                return  i;
//            }
//        }
//        return 0;

//        Arrays.sort(nums);
//        return nums[nums.length/2];

        int a = 0;
        int b = 0;
        for (int num : nums) {
            if (b == 0) {
                a = num;
            }
            if (a == num) {
                b++;
            } else {
                b--;
            }
        }
        return a;
    }

    public void rotate(int[] nums, int k) {
        if (k > nums.length) {
            k = k % nums.length;
        }
        if (k == 0) {
            return;
        }
        int[] temp = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            temp[(k + i) % nums.length] = nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = temp[i];
        }
    }


    public int maxProfit(int[] prices) {
        int max = 0;
        int min = prices[0];
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < min) {
                min = prices[i];
            } else {
                int temp = prices[i] - min;
                if (temp > max) {
                    max = temp;
                }
            }
        }
        return max;
    }

    // 792533451
    //[7,2,5,3,6,4,1,2,3,4,3,2,1]
    public int maxProfit_2(int[] prices) {
        /*int temp = 0;
        int count = 0;
        int maxprice = 0;
        int index = 0; // 持有股的索引
        for (int i = 1; i < prices.length; i++) {
            if (prices[i]<prices[index]){
                index = i;
                // 计算利润
                count += temp;
                temp = 0;
                maxprice = 0;
            }else{
                if (maxprice<prices[i]){ // 更新最大价格
                    maxprice = prices[i];
                    temp = prices[i]-prices[index];
                }else { //价格开始下降,抛售股,低价买
                    index = i;
                    count += temp;
                    temp = 0;
                    maxprice = 0;
                }
            }
        }
        return count+temp;*/
        int maxprofit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                maxprofit += prices[i] - prices[i - 1];
            }
        }
        return maxprofit;
    }

    public static boolean jump(int[] nums, int index) {
        if (nums[index] + index >= nums.length - 1) {
            return true;
        }
        // 获取能跳的最远距离
        int max = 0;
        int maxIndex = 0;
        for (int i = index + 1; i <= (nums[index] + index); i++) {
            if (nums[i] + i > max) {
                max = nums[i] + i;
                maxIndex = i;
            }
        }
        if (maxIndex == 0) {
            return false;
        }
        if (max >= nums.length - 1) {
            return true;
        }
        if (jump(nums, maxIndex)) {
            return true;
        }
        return false;
    }

    public static boolean canJump(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        int index = 0;
        int max = 0;
        while (true) {
            if (nums[index] + index >= nums.length - 1) {
                return true;
            }
            // 获取能跳的最远距离
            int maxIndex = 0;
            for (int i = index + 1; i <= (nums[index] + index); i++) {
                if (nums[i] + i > max) {
                    max = nums[i] + i;
                    maxIndex = i;
                }
            }
            if (maxIndex == 0) {
                return false;
            }
            if (max >= nums.length - 1) {
                return true;
            }
            index = maxIndex;
        }
    }

    public static int jump_2(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        int count = 0;
        int max = 0;
        int maxIndex = 0;
        int index = 0;
        while (true) {
            if (nums[index] + index >= nums.length - 1) {
                count++; // 记录步数
                return count;
            }
            maxIndex = 0; // 每次都要重置
            for (int i = index + 1; i <= (nums[index] + index); i++) {
                if (nums[i] + i > max) {
                    max = nums[i] + i;
                    maxIndex = i;
                }
            }
            if (maxIndex == 0) {
                return 0; // 没有能跳的
            }

            index = maxIndex;
            count++;
        }
    }

    public int hIndex(int[] citations) {
//        Arrays.sort(citations);
//        int length = citations.length;
//        int max = citations[length - 1];
//        int h = Math.min(max, length);
//        // 数组逆序
//        for (int i = 0; i < length / 2; i++) {
//            int temp = citations[i];
//            citations[i] = citations[length - 1 - i];
//            citations[length - 1 - i] = temp;
//        }
//
//        while (h > 0){
//            if (citations[h - 1] >= h){
//                return h;
//            }
//            h--;
//        }
//        return 0;

        //二分法(通过改变长度,来压缩查找范围)
        int left = 0;
        int right = citations.length - 1;
        int mid = 0;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (canH(citations, mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }

    public static boolean canH(int[] nums, int target) {
        int count = 0;
        for (int num : nums) {
            if (num >= target) {
                count++;
            }
        }
        if (count >= target) {
            return true;
        } else {
            return false;
        }
    }

    class RandomizedSet {
        private final static Random random = new Random();
        private final ArrayList<Integer> list = new ArrayList<Integer>();
        private final HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

        public RandomizedSet() {

        }

        public boolean insert(int val) {
            if (map.containsKey(val)) {
                return false;
            } else {
                list.add(val);
                map.put(val, list.size() - 1);
                return true;
            }
        }


        public boolean remove(int val) {
            if (!map.containsKey(val)) {
                return false;
            } else {
                // 如果仅剩一个元素
                if (list.size() == 1) {
                    list.remove(0);
                    map.remove(val);
                    return true;
                }

                // 需要保证删除的元素是最后一个元素,即索引对应
                int index = map.get(val);  // 获取索引
                int lastElement = list.get(list.size() - 1);  // 获取最后一个元素
                list.set(index, lastElement); // 将最后一个元素放到删除的位置
                list.remove(list.size() - 1);  // 删除最后一个元素
                map.put(lastElement, index); // 更新map
                map.remove(val);  // 删除map
                return true;
            }
        }

        public int getRandom() {
            return list.get(random.nextInt(list.size()));
        }
    }


    public static int[] productExceptSelf(int[] nums) {
        int[] answer = new int[nums.length];
        int count = 0;
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                count++;
                index = i;
            }
            if (count > 1) {
                for (int j = 0; j < nums.length; j++) {
                    answer[j] = 0;
                }
                return answer;
            }
        }
        if (count == 1) {
            answer[index] = 1;
            for (int i = 0; i < nums.length; i++) {
                if (i != index) {
                    answer[index] *= nums[i];
                    answer[i] = 0;
                }
            }
            return answer;
        }

//        int [] prefix = new int[nums.length];
//        prefix[0] = nums[0];
//        int [] suffix = new int[nums.length];
//        suffix[nums.length-1] = nums[nums.length-1];
//        for (int i = 1; i < nums.length; i++) {
//            prefix[i] = prefix[i-1] * nums[i];
//        }
//        for (int i = nums.length-2; i >= 0; i--) {
//            suffix[i] = suffix[i+1] * nums[i];
//        }
//        answer[0] = suffix[1];
//        answer[nums.length-1] = prefix[nums.length-2];
//        for (int i = 1; i < nums.length-1; i++) {
//            answer[i] = prefix[i-1] * suffix[i+1];
//        }
//        return answer;


        //可以在计算前缀和后缀的同时计算结果
        int prefix = 1;
        for (int i = 0; i < nums.length; i++) {
            answer[i] = prefix; // answer 存的是前缀的乘积
            prefix *= nums[i];
        }
        int suffix = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            answer[i] *= suffix; // answer 存的是最后的结果
            suffix *= nums[i];
        }
        return answer;
    }

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int product = 0;
        int need = 0;
        for (int i : gas) {
            product += i;
        }
        for (int i : cost) {
            need += i;
        }
        if (product < need) {
            return -1;
        }


//        for (int i = 0; i < gas.length; i++) {
//            if (gas[i] - cost[i] >= 0){
//                int index = i;
//                int count = 0;
//                int has = 0;
//                while (count < gas.length){
//                    has += gas[index] - cost[index];
//                    if (has < 0){
//                        i= (index + 1) % gas.length;
//                        break;
//                    }
//                    index = (index + 1) % gas.length;
//                    count++;
//                }
//                if (count >= gas.length){
//                    return i;
//                }
//            }
//        }
        int count = 0;
        int index = 0;
        int has = 0;
        int flag = 2;
        while (count < gas.length) {
            has = has + gas[index] - cost[index];
            index = (index + 1) % gas.length;
            count++;
            if (has < 0) {
                count = 0;
                has = 0;
            }
            if (index == 0) {
                flag--;
                if (flag == 0) {
                    return -1;
                }
            }
        }
        return index;
    }

    public int candy(int[] ratings) {
        int count = 0;
        int[] nums = new int[ratings.length];
        Arrays.fill(nums, 1); // 初始化数组
        if (ratings.length == 1) {
            return 1;
        } else if (ratings.length == 2) {
            return ratings[0] != ratings[1] ? 3 : 2;
        }
        count = ratings.length;
        for (int i = 0; i < ratings.length; i++) {
            if (i == 0) {
                if (ratings[i] > ratings[i + 1]) {
                    count += 1;
                    nums[i]++;
                }
            } else if (i == ratings.length - 1) {
                if (ratings[i] > ratings[i - 1]) {
                    count += 1;
                    nums[i]++;
                }
            } else {
                if (ratings[i] > ratings[i - 1] || ratings[i] > ratings[i + 1]) {
                    nums[i]++;
                    if (ratings[i] > ratings[i - 1]) {

                    }
                    int j = i;
                    count++;
                    while (ratings[j] < ratings[j - 1]) {
                        j--;
                        count++;
                    }
                }
            }
        }
        return count;
    }


    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        int[] ints = productExceptSelf(nums);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }
}